// BinaryTree.java
public class BinaryTree {
	// Root node pointer. Will be null for an empty tree.
	private Node root;

	
	
	
	private static class Node {
		Node left;
		Node right;
		int data;

		Node(int newData) {
			left = null;
			right = null;
			data = newData;
		}
	}
	

	/**
	 * Creates an empty binary tree -- a null root pointer.
	 */
	public void BinaryTree() {
		root = null;
	}
	

	/**
	 * Returns true if the given target is in the binary tree. Uses a recursive
	 * helper.
	 */
	public boolean lookup(int data) {
		return (lookup(root, data));
	}

	/**
	 * Recursive lookup -- given a node, recur down searching for the given
	 * data.
	 */
	private boolean lookup(Node node, int data) {
		if (node == null) {
			return (false);
		}

		if (data == node.data) {
			return (true);
		} else if (data < node.data) {
			return (lookup(node.left, data));
		} else {
			return (lookup(node.right, data));
		}
	}

	/**
	 * Inserts the given data into the binary tree. Uses a recursive helper.
	 */
	public void insert(int data) {
		root = insert(root, data);
	}

	/**
	 * Recursive insert -- given a node pointer, recur down and insert the given
	 * data into the tree. Returns the new node pointer (the standard way to
	 * communicate a changed pointer back to the caller).
	 */
	private Node insert(Node node, int data) {
		if (node == null) {
			node = new Node(data);
		} else {
			if (data <= node.data) {
				node.left = insert(node.left, data);
			} else {
				node.right = insert(node.right, data);
			}
		}

		return (node); // in any case, return the new pointer to the caller
	}
	
	/**
	 Build 123 using only one pointer variable.
	*/
	public void build123b() {
	  root = new Node(2);
	  root.left = new Node(1);
	  root.right = new Node(3);
	}
	
	
	
	
	
//********************************************************************	
	public Node sortedArrayToBST(int arr[], int start, int end) {
		if (start > end)
			return null;
		// same as (start+end)/2, avoids overflow.
		int mid = start + (end - start) / 2;
		Node node = new Node(arr[mid]);
		node.left = sortedArrayToBST(arr, start, mid - 1);
		node.right = sortedArrayToBST(arr, mid + 1, end);
		return node;
	}

	public void sortedArrayToBST(int arr[], int n) {
		this.root = sortedArrayToBST(arr, 0, n - 1);
	}
	//********************************************************************		

	
	
	/**
	 Tests if a tree meets the conditions to be a
	 binary search tree (BST). Uses the efficient
	 recursive helper.
	*/
	public boolean isBST2() {
	 return( isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE) );
	}

	/**
	  Efficient BST helper -- Given a node, and min and max values,
	  recurs down the tree to verify that it is a BST, and that all
	  its nodes are within the min..max range. Works in O(n) time --
	  visits each node only once.
	*/
	private boolean isBST2(Node node, int min, int max) {
	  if (node==null) {
	    return(true);
	  }
	  else {
	   // left should be in range  min...node.data
	    boolean leftOk = isBST2(node.left, min, node.data);

	    // if the left is not ok, bail out
	    if (!leftOk) return(false);

	    // right should be in range node.data+1..max
	    boolean rightOk = isBST2(node.right, node.data+1, max);

	    return(rightOk);
	  }
	} 	
	
	
	
	
	
	/**
	 Prints the node values in the "inorder" order.
	 Uses a recursive helper to do the traversal.
	*/
	public void printTree() {
	 printTree(root);
	 System.out.println();
	}

	private void printTree(Node node) {
	 if (node == null) return;

	 // left, node itself, right
	 printTree(node.left);
	 System.out.print(node.data + "  ");
	 printTree(node.right);
	} 
	
	
	/**
	 Given a binary tree, prints out all of its root-to-leaf
	 paths, one per line. Uses a recursive helper to do the work.
	*/
	public void printPaths() {
	  int[] path = new int[1000];
	  printPaths(root, path, 0);
	}

	/**
	 Recursive printPaths helper -- given a node, and an array containing
	 the path from the root node up to but not including this node,
	 prints out all the root-leaf paths.
	*/
	private void printPaths(Node node, int[] path, int pathLen) {
	  if (node==null) return;

	  // append this node to the path array
	  path[pathLen] = node.data;
	  pathLen++;

	  // it's a leaf, so print the path that led to here
	  if (node.left==null && node.right==null) {
	    printArray(path, pathLen);
	  }
	  else {
	  // otherwise try both subtrees
	    printPaths(node.left, path, pathLen);
	    printPaths(node.right, path, pathLen);
	  }
	}

	/**
	 Utility that prints ints from an array on one line.
	*/
	private void printArray(int[] ints, int len) {
	  int i;
	  for (i=0; i<len; i++) {
	   System.out.print(ints[i] + " ");
	  }
	  System.out.println();
	} 
	
	
	/**
	 Returns the number of nodes in the tree.
	 Uses a recursive helper that recurs
	 down the tree and counts the nodes.
	*/
	public int size() {
	  return(size(root));
	}

	private int size(Node node) {
	  if (node == null) return(0);
	  else {
	    return(size(node.left) + 1 + size(node.right));
	  }
	} 	
	  
}